import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
 * <p>
 * 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
 * <p>
 * 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
 * 示例 1：
 * <p>
 * 输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
 * 输出：15
 * 解释：
 * 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
 * 第 1 天：1, 2, 3, 4, 5
 * 第 2 天：6, 7
 * 第 3 天：8
 * 第 4 天：9
 * 第 5 天：10
 * <p>
 * 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
 * <p>
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(shipWithinDays(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5));
        System.out.println(shipWithinDays(new int[]{3, 2, 2, 4, 1, 4}, 3));
        System.out.println(shipWithinDays(new int[]{1, 2, 3, 1, 1}, 4));
        System.out.println(shipWithinDays(
                new int[]{299, 329, 425, 288, 97, 181, 294, 410, 220, 116, 150, 48, 228, 131, 304, 102, 341, 487, 65, 70, 419, 270, 425, 167, 131, 304, 376, 101, 319, 407, 361, 299, 146, 440, 2, 355, 402, 443, 191, 274, 397, 347, 422, 484, 292, 231, 109, 320, 403, 338, 252, 183, 435, 112, 107, 405, 302, 411, 57, 283, 463, 291, 256, 231, 163, 466, 274, 490, 341, 465, 89, 397, 399, 481, 217, 201, 431, 343, 493, 239, 83, 129, 373, 496, 137, 490, 419, 482, 216, 290, 389, 250, 453, 339, 48, 208, 170, 473, 77, 222, 355, 55, 466, 233, 88, 280, 9, 305, 184, 91, 22, 278, 17, 260, 201, 466, 150, 85, 25, 452, 156, 373, 163, 428, 429, 456, 91, 192, 396, 104, 185, 401, 202, 250, 286, 496, 287, 207, 53, 14, 75, 308, 222, 24, 98, 179, 122, 256, 29, 11, 241, 306, 82, 84, 39, 75, 75, 141, 412, 378, 83, 464, 460, 158, 388, 125, 59, 232, 196, 15, 378, 111, 453, 329, 348, 172, 113, 103, 282, 146, 26, 150, 144, 72, 126, 496, 61, 135, 264, 54, 427, 3, 177, 200, 401, 338, 269, 232, 467, 497, 304, 495, 121, 353, 489, 346, 352, 407, 262, 350, 176, 185, 65, 138, 253, 119, 409, 328, 354, 482, 451, 27, 312, 24, 218, 479, 168, 350, 87, 376, 313, 89, 145, 15, 435, 66, 111, 28, 331, 375, 453, 55, 264, 351, 355, 157, 404, 93, 346, 56, 281, 18, 436, 417, 232, 42, 380, 276, 453, 411, 480, 67, 457, 78, 221, 407, 415, 16, 383, 410, 496, 227, 151, 91, 191, 126, 447, 349, 445, 392, 301, 112, 434, 78, 243, 463, 98, 304, 285, 224, 425, 324, 287, 451, 248, 491, 252, 299, 61, 218, 434, 312, 39, 191, 34, 223, 164, 5, 117, 261, 173, 376, 94, 209, 25, 74, 329, 493, 330, 166, 304, 345, 331, 338, 116, 15, 240, 17, 232, 280, 174, 301, 98, 130, 464, 151, 237, 360, 99, 45, 137, 446, 471, 211, 462, 378, 15, 131, 49, 495, 157, 457, 437, 426, 31, 239, 72, 100, 283, 78, 123, 441, 281, 456, 53, 137, 300, 152, 489, 1, 176, 309, 416, 2, 131, 299, 420, 59, 159, 331, 207, 422, 437, 96, 240, 167, 18, 29, 101, 121, 253, 328, 48, 74, 354, 346, 351, 399, 181, 289, 299, 407, 224, 157, 156, 243, 205, 483, 96, 396, 109, 268, 236, 297, 32, 311, 374, 248, 15, 155, 149, 26, 500, 110, 107, 140, 285, 402, 58, 442, 442, 362, 460, 288, 318, 269, 4, 136, 374, 75, 418, 474, 258, 398, 70, 228, 33, 94, 282, 306, 233, 445, 95, 199, 498, 401, 429, 354, 283, 377, 496, 238, 92, 419, 387, 438, 242, 437, 433, 442, 81, 11, 415, 28, 336, 235, 3, 431, 105, 346, 156, 56, 439, 8, 300, 224, 454, 311, 261, 164, 146, 301, 180, 449, 468, 97, 121, 384, 400, 10, 165, 443, 422, 304, 430, 26, 5, 421, 398, 139, 79, 341, 413, 418, 270, 203, 7, 174, 112, 170, 135, 22, 172, 476, 438, 357, 27, 223, 236, 374, 237, 263, 258, 65, 437, 445, 215, 96, 80, 375, 228, 15, 310, 470, 83, 80, 212, 374, 200, 240, 93, 109, 415, 420, 453, 125, 7, 205, 276, 437, 486, 237, 324, 324, 226, 495, 275, 474, 438, 227, 2, 441, 288, 303, 465, 78, 416, 399}, 289));
    }

    private static Map<String, Integer> map;
    private static int min;
    private static int count = 0;

    /**
     * 动态规范，会超时
     * 如果备忘录用二维数组会超出内存限制
     *
     * @param weights
     * @param d
     * @return
     */
    public static int shipWithinDays(int[] weights, int d) {
        map = new HashMap<>(weights.length);
        int sum = 0;
        for (int weight : weights) {
            sum += weight;
        }
        min = sum / d;
        return shipWithinDays(weights, 0, d);
    }

    public static int shipWithinDays(int[] weights, int head, int d) {
        String key = head + "-" + d;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        int res = 0;
        if (d >= weights.length - head) {
            res = Arrays.stream(weights).max().getAsInt();
        } else if (d == 1) {
            // 求和
            for (int i = head; i < weights.length; i++) {
                res += weights[i];
            }
        } else {
            // 递归下去
            res = Integer.MAX_VALUE;
            int tmp = 0;
            for (int i = head; (i <= weights.length - d) && (tmp < res); i++) {
                tmp += weights[i];
                if (i + 1 < weights.length && tmp + weights[i + 1] < min) {
                    continue;
                }
                res = Math.min(res, Math.max(tmp, shipWithinDays(weights, i + 1, d - 1)));
            }
        }
        map.put(key, res);
        return res;
    }
}